Search results for "Path graph"
showing 3 items of 3 documents
An efficient algorithm for stopping on a sink in a directed graph
2013
Abstract Vertices of an unknown directed graph of order n are revealed one by one in some random permutation. At each point, we know the subgraph induced by the revealed vertices. Our goal is to stop on a sink, a vertex with no out-neighbors. We show that if a sink exists this can be achieved with probability Θ ( 1 / n ) , which is best possible.
Highly irregular graphs with extreme numbers of edges
1997
Abstract A simple connected graph is highly irregular if each of its vertices is adjacent only to vertices with distinct degrees. In this paper we find: (1) the greatest number of edges of a highly irregular graph with n vertices, where n is an odd integer (for n even this number is given in [1]), (2) the smallest number of edges of a highly irregular graph of given order.
Groups whose prime graph on conjugacy class sizes has few complete vertices
2012
Abstract Let G be a finite group, and let Γ ( G ) denote the prime graph built on the set of conjugacy class sizes of G. In this paper, we consider the situation when Γ ( G ) has “few complete vertices”, and our aim is to investigate the influence of this property on the group structure of G. More precisely, assuming that there exists at most one vertex of Γ ( G ) that is adjacent to all the other vertices, we show that G is solvable with Fitting height at most 3 (the bound being the best possible). Moreover, if Γ ( G ) has no complete vertices, then G is a semidirect product of two abelian groups having coprime orders. Finally, we completely characterize the case when Γ ( G ) is a regular …